iT邦幫忙

2022 iThome 鐵人賽
DAY 3
3
自我挑戰組

玩game學打code。街機程式設計再進化。微軟Arcade系列 第 3 篇

Arcade也能學演算法Ouo!? 演算法遊戲(1)

14th鐵人賽
766 瀏覽

  • 分享至 

  • xImage
    •  

第一篇：油漆桶遊戲-演算法篇

大綱

  • 遊戲內容
  • 經典演算法-Flood fill
  • 自製演算法-地圖生成

成果預覽

在arcade的效果

在console的效果

經典演算法Flood fill

Flood fill 是什麼阿
Flood fill是一個用在圖像渲染的簡單演算法
藉由遞迴搜尋周圍相同顏色的單位對其執行動作

下面是演算法示意圖
image alt

上圖是由 André Karwath aka Aka - 自己的作品, CC BY-SA 2.5
https://commons.wikimedia.org/w/index.php?curid=481651

接下來就上程式碼吧

function flood_fill(old, chg, x, y) { // old: 舊顏色, chg: 新顏色, x: x座標, y: y座標
    if (map[x][y] == chg) { // 如果新顏色和舊顏色相同，則不再改變
        return
    }
    if (map[x][y] == old) { // 如果舊顏色和目標顏色相同，則改變
        map[x][y] = chg; // 改變顏色
        if (x > 0) { 
            flood_fill(old, chg, x - 1, y);
        }
        if (x < map.length - 1) {
            flood_fill(old, chg, x + 1, y);
        }
        if (y > 0) {
            flood_fill(old, chg, x, y - 1);
        }
        if (y < map.length - 1) {
            flood_fill(old, chg, x, y + 1);
        }
    } else {
        return;
    }
}

解析一下

有些人可能不知道什麼是遞迴，在這邊補充一下，
簡單來說遞迴就是在函式內呼叫函式本身，
透過不斷疊層後達成目的

首先

if (map[x][y] == chg) { // 如果新顏色和舊顏色相同，則不再改變
        return
    }

這邊主要是做個防呆，避免重複執行浪費資源，節省不必要的錯誤。

if (map[x][y] == old) { // 如果舊顏色和目標顏色相同，則改變
        map[x][y] = chg; // 改變顏色
        if (x > 0) { 
            flood_fill(old, chg, x - 1, y);
        }
        if (x < map.length - 1) {
            flood_fill(old, chg, x + 1, y);
        }
        if (y > 0) {
            flood_fill(old, chg, x, y - 1);
        }
        if (y < map.length - 1) {
            flood_fill(old, chg, x, y + 1);
        }
    } else {
        return;
    }

這邊就是演算法本人拉
往周圍尋找，尋找相鄰的是不是同一種的。
前文提到Flood fill是尋找周圍相同性質的單位並對其執行動作。
我們是填色遊戲，目的是變成相同顏色，所以我用map[x][y] = chg來改變這個像素的顏色，然後往四周尋找。
如果找的地方不是跟原來相同性質的，就代表遇到邊界了所以原地折返

自製地圖生成演算法

既然地圖不是亂數生成，特別寫一個演算法那就要有要達成的目的。
我想要做到

  1. 可以控制顏色的數量
  2. 可以設定顏色的分散程度

想好之後就來動工拉 先設定參數

color_number = 9;
dispersion = 0.9;
map_width = 10;
map_height = 10;

由上到下 依序是顏色的數量 分散的程度 地圖的寬和高
有了參數之後先生成空白地圖

var map = [];
for (let i = 0; i < map_width; i++) {
    map.push([]);
    for (let j = 0; j < map_height; j++) {
        map[i].push(0);
    }
}

這樣 你就得到了一個叫做map的10*10陣列了
再來我還需要做一件事，那就是生成隨機的圖塊。

function make_area(x, y, area_color, count) {
    let now_x = x;
    let now_y = y;
    for (let i = 0; i < count; i++) {
        ...
    }
}

我的想法是從一個起始點開始，接著讓那個點移動。
移動的路徑就是生成的圖塊，生成的次數則由count控制

if (map[now_x][now_y] == area_color) {
    i+1;
}
map[now_x][now_y] = area_color;

如果剛好找到的點是相同顏色的 則不計數
然後利用map[now_x][now_y] = area_color來上色
最後就是在找個方向延伸下去

function make_area(x, y, area_color, count) {
    let now_x = x;
    let now_y = y;
    for (let i = 0; i < count; i++) {
        if (map[now_x][now_y] == area_color) {
            i+1;
        }
        map[now_x][now_y] = area_color;
        let direction = Math.floor(Math.random() * 4);
        if (direction == 0 && now_x > 0) {
            now_x -= 1;
        } else if (direction == 1 && now_x < map.length - 1) {
            now_x += 1;
        } else if (direction == 2 && now_y > 0) {
            now_y -= 1;
        } else if (direction == 3 && now_y < map.length - 1) {
            now_y += 1;
        }
    }
}

這邊用到js的math
Math.random() 可以生成0-1之間的數，乘以x再取整就可以獲得0到x-1的數了

最後讓我們利用今天所學，做一個console遊戲當作今天的結尾吧

/*
* AUTHOR rlongdragon
* DATE 2022-09-16
* VISON 1.0
* 
* this probject used copilot
*/


//import
const readline = require("readline"); // 載入readline模組

//set up 
color_number = 3; // 色彩的數量
dispersion = 0.5; // 分散度
map_width = 20;   // 地圖寬度
map_height = 20;  // 地圖高度

// 地圖初始化
var map = [];
for (let i = 0; i < map_width; i++) {
    map.push([]);
    for (let j = 0; j < map_height; j++) {
        map[i].push(0);
    }
}
// 生成斑點
function make_area(x, y, area_color, count) {
    let now_x = x; // 生成斑點的x座標
    let now_y = y; // 生成斑點的y座標
    for (let i = 0; i < count; i++) { // 嘗試生成count次
        if (map[now_x][now_y] == area_color) { // 如果已經是目標顏色，則不再生成
            i + 1;
        }
        map[now_x][now_y] = area_color; // 生成斑點
        let direction = Math.floor(Math.random() * 4);  // 隨機製造下次生成的方向
        if (direction == 0 && now_x > 0) {
            now_x -= 1;
        } else if (direction == 1 && now_x < map.length - 1) {
            now_x += 1;
        } else if (direction == 2 && now_y > 0) {
            now_y -= 1;
        } else if (direction == 3 && now_y < map.length - 1) {
            now_y += 1;
        }
    }
}
// 地圖生成
function create_map() {
    for (let i = 0; i < map.length; i++) {
        for (let j = 0; j < map.length; j++) {
            if (Math.random() > dispersion * 0.95) { // 有機率生成斑點
                make_area(i, j, Math.floor(Math.random() * color_number), Math.floor((Math.random() + 1) * 5) * dispersion);
            }
        }
    }
}
// 輸出地圖
function print_map(map) {
    for (let i = 0; i < map.length; i++) { // 輸出地圖
        let row = ""; // 一行的字串
        for (let j = 0; j < map.length; j++) { // 輸出一行
            if (j == map.length - 1) { // 如果是最後一個，則不加空格
                row += map[i][j]; // 加入地圖的數字
            } else { // 如果不是最後一個，則加空格
                row += map[i][j] + " "; // 加入地圖的數字
            } 
        }
        console.log(row);
    }
}

//flood fill 演算法
function flood_fill(old, chg, x, y) { // old: 舊顏色, chg: 新顏色, x: x座標, y: y座標
    if (map[x][y] == chg) { // 如果新顏色和舊顏色相同，則不再改變
        return
    }
    if (map[x][y] == old) { // 如果舊顏色和目標顏色相同，則改變
        map[x][y] = chg; // 改變顏色
        if (x > 0) { 
            flood_fill(old, chg, x - 1, y);
        }
        if (x < map.length - 1) {
            flood_fill(old, chg, x + 1, y);
        }
        if (y > 0) {
            flood_fill(old, chg, x, y - 1);
        }
        if (y < map.length - 1) {
            flood_fill(old, chg, x, y + 1);
        }
    } else {
        return;
    }
}
// 檢查是否結束
function check_end() { 
    let end = true;
    color = map[0][0]; // 設定初始顏色
    for (let i = 0; i < map.length; i++) {
        for (let j = 0; j < map.length; j++) {
            if (map[i][j] != color) { // 如果有不同的顏色，則還沒結束
                end = false;
                return end;
            }
        }

    }
    return end;
}

//main
create_map(); // 生成地圖
print_map(map); // 輸出地圖
var rl = readline.createInterface({ // 載入readline模組
    input: process.stdin,
    output: process.stdout
});
rl.on('line', function (line) {  // 輸入
    let color = parseInt(line); // 輸入的顏色
    flood_fill(map[0][0], color, 0, 0); // 塗色
    print_map(map); // 輸出地圖
    if (check_end()) { // 檢查是否結束
        console.log("you win");
        process.exit(); // 結束程式
    }
});

下期預告

油漆桶遊戲-實作篇
>_將理論實踐到Arcade 發生什麼事呢

作者：鍾佳龍

上一篇
Arcade再進化－手把手帶你安裝Arcade遊戲機
下一篇
Arcade再進化 - 空島跳躍者(1)
系列文
玩game學打code。街機程式設計再進化。微軟Arcade 共 30 篇
  1. 26
    Arcade再進化-橫向捲軸遊戲(4)
  2. 27
    Arcade再進化-空島跳躍者(5)
  3. 28
    Arcade再進化-社群遊戲大集合(上)
  4. 29
    Arcade也能學演算法Ouo!? 演算法遊戲(5)
  5. 30
    Arcade再進化-社群遊戲大集合(下)
完整目錄
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
1064 組
團體組數
40 組
累計文章數
22090 篇
完賽人數
594 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js
熱門問題
熱門回答
熱門文章
IT邦幫忙